소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

제한사항

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀이

첫 번째 풀이 (시간 초과)

def isPrime(n):
    if n == 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False

    return True

def solution(n):
    count = 0
    for i in range(1, n + 1):
        if isPrime(i):
            count += 1

    return count

첫 번째 시도는 2부터 n-1까지 반복문을 돌면서 한 번이라도 나누어떨어지지 않으면 소수로 판단하도록 구현했습니다.

즉, 1과 자기 자신을 제외하고 어떤 수로 나누어떨어지는지, 나누어떨어지지 않는지 판단하는 소수 판별 함수를 구현해서

시도했는데 시간 초과가 발생했습니다.

n의 최댓값이 100만인데 저 방법으로 시도하면 대충 1조 번 정도 연산하리라 추정했습니다.

1초가 넘어가면 시간 초과로 실패하는 듯 보였고 연산이 1억을 넘어가면 1초를 넘어가는 것으로 알고 있어서 저 방법으로는 안 되겠다고 판단을 내렸습니다.

문제가 좀 너무하다고 느꼈던 게, 시간제한이라도 적혀 있었으면 시간복잡도를 생각해 보고 처음부터 에라토스테네스의 체로 풀었을 텐데 기입된 게 전혀 없었다는 점입니다.

두 번째 풀이

def solution(n):
    check = [False] * 1000001
    count = 0
    for i in range(2, n + 1):
        if check[i]: continue
        count += 1
        for j in range(i, n + 1, i):
            check[j] = True

    return count

두 번째 방법은 에라토스테네스의 체를 이용하여 풀었습니다.

알고리즘 원리는 다음과 같습니다.

• check 리스트를 만들어서 모두 False 값으로 초기화한다.
• 값에 해당하는 check 리스트가 False라면 소수이므로 하나 카운트한다.
• 카운트한 후에 값의 배수를 모두 True로 채워 넣는다.
• 값에 해당하는 check 리스트가 True라면 소수가 아니므로 continue

앞으로 특정 값이 소수인지 판별만 하면 되는 문제면 첫 번째 풀이 방법으로 풀 것 같고, 특정 범위의 소수의 개수를 모두 세야 한다면 에라토스테네스의 체를 사용하여 문제를 풀 것 같습니다.